package com.fosss.sort;

import java.util.Arrays;

/**
 * 堆排序
 */
public class HeapSort {
    public static void main(String[] args) {
//        int[] arr = {4, 6, 8, 5, 9};
//        heapSort(arr);

        //测试时间复杂度
        //创建一个80000条数据的数组
        int[] arr=new int[80000];
        for(int i = 0; i <80000;i++){
            arr[i]=(int)(Math.random()*80000);
        }
        long startTime = System.currentTimeMillis();
        heapSort(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("花费时间"+(endTime-startTime)+"毫秒");
    }

    public static void heapSort(int[] arr) {
        System.out.println("堆排序");
        //i=arr.length/2-1最后一个非叶子结点
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapTransfer(arr, i, arr.length);
        }

        //将堆顶元素与末尾元素交换，数组长度递减是为了将已经挑出来的最值过滤掉，然后重复转化成大堆顶的过程
        for(int j=arr.length-1;j>0;j--){
            int temp=arr[j];
            arr[j]=arr[0];
            arr[0]=temp;
            heapTransfer(arr,0,j);//
        }

//        System.out.println(Arrays.toString(arr));

    }

    /**
     * 将数组（二叉树）转化成大顶堆
     *
     * @param arr    数组
     * @param i      非叶子结点的索引
     * @param length 数组长度
     */
    public static void heapTransfer(int[] arr, int i, int length) {
        //2*i+1为左子树，2*i+2为右子树
        int temp = arr[i];

        for (int k = 2 * i + 1; k < length; k=2*k+1) {

            //找到左右子树中较大的那个
            if ((k + 1 < length) && arr[k] < arr[k + 1]) {
                k++;
            }

            if (arr[k] > temp) {
                arr[i] = arr[k];
                i = k;//为了进行下一次循环
            } else {
                break;
            }
        }
        arr[i] = temp;
    }

}






























